#include<iostream>
using namespace std;
typedef long long LL;

LL qmi(LL a,LL k,LL p){
    LL ans=1;
    while(k){
        if(k&1)ans=(LL)ans*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    
    return ans%p;
    
}


int main(){
    int n;
    cin>>n;
    while(n--){
        long long a,k,p;
        cin>>a>>k>>p;
        
        cout<<qmi(a,k,p)<<endl;
    }
    
    
    return 0;
}
